import java.util.ArrayList;
import java.util.Random;

import PuzzlePieces.SudokuPuzzle;


public class SudokuSolver {

	private SudokuPuzzle puzzle;
	private Random myGenerator = new Random();
	private static long startTime;
	private static long stopTime;
	
	
	public SudokuSolver(SudokuPuzzle myPuzzle) {
		puzzle = myPuzzle;
	}

	public static void main(String[] args){
		System.out.println("Starting Solver");
		SudokuPuzzle myPuzzle = null;
		if(args.length > 0){
			myPuzzle = new SudokuPuzzle(args[0]);
		}else{
			myPuzzle = new SudokuPuzzle("hard.txt");
		}
		System.out.println();
		System.out.println("Blank Unsolved Puzzle: ");
		System.out.println();
		System.out.println(myPuzzle.toString());
		System.out.println();
		SudokuSolver mySolver = new SudokuSolver(myPuzzle);
		startTime = System.currentTimeMillis();
		mySolver.solve();
		stopTime = System.currentTimeMillis();
		System.out.println(myPuzzle.toString());
		System.out.println();
		double time = ((double)(stopTime - startTime)) / ((double)1000);
		System.out.println("Time taken: "+time+" seconds");
	}

	private boolean findAnswer(boolean changed) {
		if(puzzle != null){
			for(int row = 0; row < 9; row++){
				for(int col = 0; col < 9; col++){

					if(puzzle.checkZero(row, col)){
						if(changed){
							ArrayList<Integer> myTempNumbers = puzzle.getAvailNumbers(row, col);
							if(myTempNumbers.size() == 1)
								puzzle.setNumber(myTempNumbers.get(0), row, col);
							if(puzzle.checkZero(row, col))
								boxAlg1(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg2(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg3(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg4(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg5(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg6(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg7(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg8(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg9(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg10(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg11(row, col);
							
							if(puzzle.checkZero(row, col))
								boxAlg12(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg13(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg14(row, col);
							if(puzzle.checkZero(row, col))
								boxAlg15(row, col);
							if(puzzle.checkZero(row, col))
								lineAlg1(row, col);
							
							puzzle.commit();
						
						}else{
							if(!randomGenerate(row, col)){
								return false;
							}
						}
					}

					
				}
			}
		}
		return puzzle.isCorrect();
	}
	
	private void lineAlg1(int row, int col){
		//optimize!!!!!!!!!
		int rowZeros[] = getZeros(puzzle.getRow(row).getNumbers());
		int colZeros[] = getZeros(puzzle.getCol(col).getNumbers());
		ArrayList<Integer> myNumbers = new ArrayList<Integer>();
		for(int i = 0; i < colZeros.length; i++){
			myNumbers.clear();
			if(colZeros.length > 2){
				myNumbers = findCommonNumbers(puzzle.getAvailNumbers(colZeros[i], col), puzzle.getRow(colZeros[(i+1)%(colZeros.length)]).getUsedNumbers());
				myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(colZeros[i], col).getUsedNumbers());
				myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(colZeros[(i+1)%(colZeros.length)], col).getUsedNumbers());
				for(int j = (i+2); j < (colZeros.length+i); j++){
					myNumbers = findCommonNumbers(myNumbers, puzzle.getRow(colZeros[(j%(colZeros.length))]).getUsedNumbers());
					myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(colZeros[(j%(colZeros.length))], col).getUsedNumbers());
				}	
			}else if(colZeros.length > 1){
				myNumbers = findCommonNumbers(puzzle.getAvailNumbers(colZeros[i], col), puzzle.getRow(colZeros[(i+1)%(colZeros.length)]).getUsedNumbers());
				myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(colZeros[i], col).getUsedNumbers());
				myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(colZeros[(i+1)%(colZeros.length)], col).getUsedNumbers());
			}
			
			if(myNumbers.size() == 1){
				if(!puzzle.checkZero(colZeros[i], col))
					puzzle.setNumber(myNumbers.get(0), colZeros[i], col);
			}

		}
		
		for(int i = 0; i < rowZeros.length; i++){
			myNumbers.clear();
			if(rowZeros.length > 2){
				myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, rowZeros[i]), puzzle.getCol(rowZeros[(i+1)%(rowZeros.length)]).getUsedNumbers());
				myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(row, rowZeros[i]).getUsedNumbers());
				myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(row, rowZeros[(i+1)%(rowZeros.length)]).getUsedNumbers());
				for(int j = (i+2); j < (rowZeros.length+i); j++){
					myNumbers = findCommonNumbers(myNumbers, puzzle.getCol(rowZeros[(j%(rowZeros.length))]).getUsedNumbers());
					myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(row, rowZeros[(j%(rowZeros.length))]).getUsedNumbers());
				}
			}else if(rowZeros.length > 1){
				myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, rowZeros[i]), puzzle.getCol(rowZeros[(i+1)%(rowZeros.length)]).getUsedNumbers());
				myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(row, rowZeros[i]).getUsedNumbers());
				myNumbers = findCommonNumbers(myNumbers, puzzle.getBox(row, rowZeros[(i+1)%(rowZeros.length)]).getUsedNumbers());
			}
			if(myNumbers.size() == 1){
				if(!puzzle.checkZero(row, rowZeros[i]))
					puzzle.setNumber(myNumbers.get(0), row, rowZeros[i]);
			}
		}
	
	}
	
	private int[] getZeros(int[] line){
		ArrayList<Integer> myZeros = new ArrayList<Integer>();
		for(int i = 0; i < line.length; i++){
			if(line[i] == 0){
				myZeros.add(i);
			}
		}
		int zeros[] = new int[myZeros.size()];
		int i = 0;
		for(Integer num : myZeros){
			zeros[i] = num.intValue();
			i++;
		}
		return zeros;
	}
	
	private void boxAlg1(int row, int col) {
		// TODO Auto-generated method stub
		ArrayList<Integer> myNumbers = new ArrayList<Integer>();
		
		if(!puzzle.checkZero(row, puzzle.getCol(col).getLeftCol().getID())){
			if(!puzzle.checkZero(row, puzzle.getCol(col).getRightCol().getID())){

				myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), 
						puzzle.getUsedNumbers(puzzle.getRow(row).getLeftRow(), puzzle.getRow(row).getRightRow()));

				if(myNumbers.size() == 1){
					puzzle.setNumber(myNumbers.get(0), row, col);
				}
			}
		}
		
	}

	private void boxAlg2(int row, int col){
		
		ArrayList<Integer> myNumbers = new ArrayList<Integer>();
		
		if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), col)){
			if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), col)){
				myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), 
						puzzle.getUsedNumbers(puzzle.getCol(col).getLeftCol(), puzzle.getCol(col).getRightCol()));
				
				if(myNumbers.size() == 1){
					puzzle.setNumber(myNumbers.get(0), row, col);
				}
			}
		}
	}
	


	private void boxAlg3(int row, int col){
		ArrayList<Integer> myNumbers = new ArrayList<Integer>();
		if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), col)){
			if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), col)){
				if(!puzzle.checkZero(row, puzzle.getCol(col).getLeftCol().getID())){
					if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), puzzle.getCol(col).getLeftCol().getID())){
						if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), puzzle.getCol(col).getLeftCol().getID())){

							myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), 
									puzzle.getCol(col).getRightCol().getUsedNumbers());
							
							if(myNumbers.size() == 1){
								puzzle.setNumber(myNumbers.get(0), row, col);
							}
						}
					}
				}
			}
		}
	}
	
	private void boxAlg4(int row, int col){
		ArrayList<Integer> myNumbers = new ArrayList<Integer>();
		if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), col)){
			if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), col)){
				if(!puzzle.checkZero(row, puzzle.getCol(col).getRightCol().getID())){
					if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), puzzle.getCol(col).getRightCol().getID())){
						if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), puzzle.getCol(col).getRightCol().getID())){

							myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), 
									puzzle.getCol(col).getLeftCol().getUsedNumbers());
							
							if(myNumbers.size() == 1){
								puzzle.setNumber(myNumbers.get(0), row, col);
							}
						}
					}
				}
			}
		}
	}
	
	private void boxAlg5(int row, int col){
		ArrayList<Integer>myNumbers = new ArrayList<Integer>();
		if(!puzzle.checkZero(row, puzzle.getCol(col).getLeftCol().getID())){
			if(!puzzle.checkZero(row, puzzle.getCol(col).getRightCol().getID())){
				if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), col)){
					if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), puzzle.getCol(col).getLeftCol().getID())){
						if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), puzzle.getCol(col).getRightCol().getID())){
							
							myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), 
									puzzle.getRow(row).getRightRow().getUsedNumbers());
							
							if(myNumbers.size() == 1){
								puzzle.setNumber(myNumbers.get(0), row, col);
							}
						}
					}
				}
			}
		}
	}
	
	private void boxAlg6(int row, int col){
		ArrayList<Integer>myNumbers = new ArrayList<Integer>();
		if(!puzzle.checkZero(row, puzzle.getCol(col).getLeftCol().getID())){
			if(!puzzle.checkZero(row, puzzle.getCol(col).getRightCol().getID())){
				if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), col)){
					if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), puzzle.getCol(col).getLeftCol().getID())){
						if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), puzzle.getCol(col).getRightCol().getID())){
							
							myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), 
									puzzle.getRow(row).getLeftRow().getUsedNumbers());
							
							if(myNumbers.size() == 1){
								puzzle.setNumber(myNumbers.get(0), row, col);
							}
						}
					}
				}
			}
		}
	}
	
	private void boxAlg7(int row, int col){
		ArrayList<Integer> rowUsed;
		ArrayList<Integer> colUsed;
		ArrayList<Integer> myNumbers;
		
		rowUsed = puzzle.getUsedNumbers(puzzle.getRow(row).getLeftRow(), puzzle.getRow(row).getRightRow());
		colUsed = puzzle.getUsedNumbers(puzzle.getCol(col).getLeftCol(), puzzle.getCol(col).getRightCol());
		myNumbers = findCommonNumbers(rowUsed, colUsed);
		myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
		
		if(myNumbers.size() == 1){
			puzzle.setNumber(myNumbers.get(0), row, col);
		}
		
	}
	
	private void boxAlg8(int row, int col){
		ArrayList<Integer> myNumbers;
		if(!puzzle.checkZero(row, puzzle.getCol(col).getRightCol().getID())){
			if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), col)){
				if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), puzzle.getCol(col).getRightCol().getID())){
					
					myNumbers = puzzle.getUsedNumbers(puzzle.getRow(row).getLeftRow(), puzzle.getCol(col).getLeftCol());
					myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
					if(myNumbers.size() == 1){
						puzzle.setNumber(myNumbers.get(0), row, col);
					}
					
				}
			}
		}
	}
	
	private void boxAlg9(int row, int col){
		ArrayList<Integer> myNumbers;
		if(!puzzle.checkZero(row, puzzle.getCol(col).getLeftCol().getID())){
			if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), col)){
				if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), puzzle.getCol(col).getLeftCol().getID())){
					
					myNumbers = puzzle.getUsedNumbers(puzzle.getRow(row).getLeftRow(), puzzle.getCol(col).getRightCol());
					myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
					
					if(myNumbers.size() == 1){
						puzzle.setNumber(myNumbers.get(0), row, col);
					}
					
				}
			}
		}
	}
	
	private void boxAlg10(int row, int col){
		ArrayList<Integer> myNumbers;
		if(!puzzle.checkZero(row, puzzle.getCol(col).getLeftCol().getID())){
			if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), col)){
				if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), puzzle.getCol(col).getLeftCol().getID())){
					
					myNumbers = puzzle.getUsedNumbers(puzzle.getRow(row).getRightRow(), puzzle.getCol(col).getRightCol());
					myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
					
					if(myNumbers.size() == 1){
						puzzle.setNumber(myNumbers.get(0), row, col);
					}
					
				}
			}
		}
	}
	
	private void boxAlg11(int row, int col){
		ArrayList<Integer> myNumbers;
		if(!puzzle.checkZero(row, puzzle.getCol(col).getRightCol().getID())){
			if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), col)){
				if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), puzzle.getCol(col).getRightCol().getID())){
					
					myNumbers = puzzle.getUsedNumbers(puzzle.getRow(row).getRightRow(), puzzle.getCol(col).getLeftCol());
					myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
					
					if(myNumbers.size() == 1){
						puzzle.setNumber(myNumbers.get(0), row, col);
					}
					
				}
			}
		}
	}
	
	private void boxAlg12(int row, int col){
		ArrayList<Integer> myNumbers;
		if(!puzzle.checkZero(row, puzzle.getCol(col).getRightCol().getID())){
			
			myNumbers = findCommonNumbers(puzzle.getUsedNumbers(puzzle.getRow(row).getLeftRow(), puzzle.getRow(row).getRightRow()), 
					puzzle.getCol(col).getLeftCol().getUsedNumbers());
			myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
			
			if(myNumbers.size() == 1){
				puzzle.setNumber(myNumbers.get(0), row, col);
			}
		}
	}
	
	private void boxAlg13(int row, int col){
		ArrayList<Integer> myNumbers;
		if(!puzzle.checkZero(row, puzzle.getCol(col).getLeftCol().getID())){
			
			myNumbers = findCommonNumbers(puzzle.getUsedNumbers(puzzle.getRow(row).getLeftRow(), puzzle.getRow(row).getRightRow()), 
					puzzle.getCol(col).getRightCol().getUsedNumbers());
			myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
			
			if(myNumbers.size() == 1){
				puzzle.setNumber(myNumbers.get(0), row, col);
			}
		}
	}
	
	private void boxAlg14(int row, int col){
		ArrayList<Integer> myNumbers;
		if(!puzzle.checkZero(puzzle.getRow(row).getLeftRow().getID(), col)){
			
			myNumbers = findCommonNumbers(puzzle.getUsedNumbers(puzzle.getCol(col).getLeftCol(), puzzle.getCol(col).getRightCol()), 
					puzzle.getRow(row).getRightRow().getUsedNumbers());
			myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
			
			if(myNumbers.size() == 1){
				puzzle.setNumber(myNumbers.get(0), row, col);
			}
		}
	}
	
	private void boxAlg15(int row, int col){
		ArrayList<Integer> myNumbers;

		if(!puzzle.checkZero(puzzle.getRow(row).getRightRow().getID(), col)){
			
			myNumbers = findCommonNumbers(puzzle.getUsedNumbers(puzzle.getCol(col).getLeftCol(), puzzle.getCol(col).getRightCol()), 
					puzzle.getRow(row).getLeftRow().getUsedNumbers());
			myNumbers = findCommonNumbers(puzzle.getAvailNumbers(row, col), myNumbers);
			
			if(myNumbers.size() == 1){
				puzzle.setNumber(myNumbers.get(0), row, col);
			}
		}
	}
	
	
	
	private void solve(){
		boolean changed = true;
		while(!findAnswer(changed)){
			//findAnswer();
			//System.out.println(puzzle.tempString());
			//System.out.println();
			if(changed){
				//puzzle.commit();
				changed = puzzle.isChanged();
				if(!changed){
					System.out.println("Puzzle Solved with only Algorithms :");
					System.out.println();
					System.out.println(puzzle.tempString());
				}
			}
			puzzle.reset();
		}
		if(!changed)
			System.out.println("Puzzle Finished with brute force random generator : ");
		else
			System.out.println("Puzzle Solved with only Algorithms : ");
		System.out.println();
		puzzle.commit();
	}
	
	private boolean randomGenerate(int row, int col){
		ArrayList<Integer> myNumbers;
		boolean result = false;
		myNumbers = puzzle.getAvailNumbers(row, col);
		if(myNumbers.size() > 0){
			int choice = myGenerator.nextInt(myNumbers.size());
			puzzle.setNumber(myNumbers.get(choice), row, col);
			result = true;
		}
		
		return result;
	}
	
	private ArrayList<Integer> findCommonNumbers(
			ArrayList<Integer> availNumbers, ArrayList<Integer> usedNumbers) {
		
		ArrayList<Integer> myNewNumbers = new ArrayList<Integer>();
		myNewNumbers.clear();
		
		for(Integer num : availNumbers){
			if(usedNumbers.contains(num)){
				myNewNumbers.add(num);
			}
		}
		
		return myNewNumbers;
	}
	
	private ArrayList<Integer> disjointAvailableNumbers(ArrayList<Integer> aList, ArrayList<Integer> bList){
		ArrayList<Integer> myNumbers = new ArrayList<Integer>();
		int arraySize = aList.size();
		if(arraySize < bList.size()){
			arraySize = bList.size();
		}
		for(int i = 0; i < 9; i++){
			
			if(i < aList.size()){
				if(bList.contains(aList.get(i))){
					myNumbers.add(aList.get(i));
				}
			}/*
			if(i < bList.size()){
				if(aList.contains(bList.get(i))){
					myNumbers.add(new Integer(bList.get(i)));
				}
			}*/
		}
		
		
		return myNumbers;
	}
	
	private ArrayList<Integer> intersectAvailableNumbers(ArrayList<Integer> aList, ArrayList<Integer> bList){
		ArrayList<Integer> myNumbers = new ArrayList<Integer>();
		
		int arraySize = aList.size();
		if(arraySize < bList.size()){
			arraySize = bList.size();
		}
		for(int i = 0; i < arraySize; i++){
			
			if(i < aList.size()){
				if(!bList.contains(aList.get(i))){
					myNumbers.add(aList.get(i));
				}
			}
			if(i < bList.size()){
				if(!aList.contains(bList.get(i))){
					myNumbers.add(bList.get(i));
				}
			}
		}
		
		return myNumbers;
	}
	
}
